This invention relates to an apparatus and method for performing Fourier transformations on a set of digital data. More specifically, it relates to a processor for computing the Fast Fourier Transform (FFT) of discrete signals sampled from a continuously received electronic signal. Techniques for computing FFTs involve the rapid computation of multiple Discrete Fourier Transforms (DFTs). The DFT is the tool used to describe the relationship between the time domain and frequency domain representations of discrete signals.
Devices and methods for performing FFTs derive their efficiency from the relationship of the number of data words to be transformed (N) to the number of operations required to compute the DFT (N.sup.2). If a large DFT can be replaced by multiple small DFTs (e g., with radix R of 2 or 4), the number of operations required can be substantially redeuced. Further, the computation of multiple small DFTs is a multistage process, with each stage having similar steps. This allows the processor calculating the FFT to have fewer unique components. The number of stages (B) is related to the sample size and the radix by: B=Log.sub.R N. A large number of stages, however, can increase computational complexity and reduce the accuracy of the results due to round-off errors. Therefore, to increase processing efficiency through increased sample size N, methods for performing FFT have been driven to a compromise between the DFT radix R and number of stages B, with the radix generally limited to 4 or 8 by the complexity and cost of the switching in the data paths.
Several distinct methods for performing FFTs have been discussed in the prior art and have resulted in dissimilar architectures when implemented in hardware. The first was devised by Cooley and Tukey (Cooley, J. W. and Tukey, J. W., "An Algorithm for the Machine Calculation of Complex Fourier Series", Math Comput., Vol. 19, April 1965, pp. 297-301). This type has "variable geometry", meaning that data addressing changes from stage to stage.
The second type is the "constant geometry" type, introduced by Pease (Pease, M. C., "An Adaptation of the Fast Fourier Transform for Parallel Processing", Journal of the Association for Computing Machinery, Vol. 15, April 1968, pp. 252-264). The addressing of data remains the same from stage-to-stage. The only price for achievement of this simplification of the resulting hardware architecture is a change in ordering of the read-only-memory (ROM) "twiddle factors" relative to those in the variable geometry type. In both types, the ROM factors ordering will change from stage to stage, and this is generally handled with address counters.
A more recent development is the introduction of "pipeline processors". This architecture divides the computing load into successive parallel stages, allowing simultaneous processing of R channels. One well known example of a pipeline processor in a variable geometry architecture is credited to McClellan and Purdy, (McClellan, J. H. and Purdy, R. J., "Applications of Digital Signal Processing", pp. 268-278, Alan V. Oppenheim, editor, 1978, Prentice Hall). In order to keep up with the rate of parallel data input, the computational elements in each stage are themselves 4-point FFTs (instead of DFTs) with 2 stages, each with 4 arithmetic processors per stage. However, as the radix increases to 8 or higher to provide more parallelism, the increasing number of commutator or cross-bar switches becomes prohibitively expensive.
A pipelined FFT processor using the constant geometry architecture has been developed by Corinthios (Corinthios, M. J., "The Design of a Class of Fast Fourier Transform Computers" IEEE Transactions on Computers, Vol. C-20, June 1971, pp. 617-623). This architecture also requires switching and gating for cross channel communication. It also has complex and large memory requirements which become more unwieldy as the radix increases (i.e., memory length is a function of N/R.sup.2, therefore the number of memory units required is R.sup.2) Implementations of this processor are disclosed in the Corinthios U.S. Pat. No. 3,754,128 dated Aug. 21, 1973, and in "A Parallel Radix-4 Fast Fourier Transform Computer", IEEE Transaction On Computers, Vol. C-24, January 1975, pp. 80-92.
Other developments have focused on particular features of the devices and methods just described. The Perry U.S Pat. No. 4,159,528, dated June 26, 1979, introduces a correction for the phase shift introduced by the Fourier transform. The technique uses a barrel switch and delay elements to make the proper phase correction to outputs from small DFTs before combining them in a larger Fourier transform. The McGee U.S. Pat. No. 4,534,009, dated Aug. 6, 1985, implements the McClellan and Purdy architecture and discloses the use of switches and shift registers to increase the arithmetic efficiency of the computational units.
All of the single and multichannel FFT processor architectures just described require some type of interchannel communication path using switches. These paths can dynamically change with time, and with the stage in the variable geometry case.
It is accordingly an object of the present invention to provide an apparatus for performing the FFT of digital data without switches in the cross channel communication paths.
It is another object of the present invention to provide an apparatus for performing the FFT of digital data by implementing a new systolic geometry method where the stage-to-stage structure is substantially duplicated.
It is still another object of the present invention to provide an apparatus for performing the FFT of digital data where the radix size is not limited by complexity and/or cost of the switching arrangement.
It is yet another object of the present invention to provide an apparatus for performing the FFT of digital data that utilizes the phase shifting property of the Fourier transform for part of the data shuffling.
It is a further object of the present invention to provide a method for performing the FFT of digital data without a step for switching data in cross channel communication paths.
These and many other objects and advantages will be readily apparent to one skilled in the art to which the invention pertains from a perusal of the claims and the following detailed description of the preferred embodiments when read in conjunction with the appended drawings.